package com.zejian.structures.jichu;

import java.util.Arrays;

/**
 * * @author  李某
 * * @date  2021/12/18 14:42
 * * 物有本末，事有终始。知其先后者，则近道亦。
 * * 荷花开满池塘的前一天，还是半塘荷花，半塘云！
 */


public class CountSort {

    public static void countSort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;

        int max = max(arr);

        int[] count = new int[max+1];
        Arrays.fill(count, 0);

        for(int i=0; i<arr.length; i++) {
            count[arr[i]] ++;
        }

        int k = 0;
        for(int i=0; i<=max; i++) {
            for(int j=0; j<count[i]; j++) {
                arr[k++] = i;
            }
        }

    }

    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for(int ele : arr) {
            if(ele > max)
                max = ele;
        }

        return max;
    }

}
